package com.zk.algorithm;

import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.LinkedList;
import java.util.Queue;

@LeetCodeExplore
@Hard
public class CourseSchedule {

    public static void main(String...args) {
        Utils.println(new CourseSchedule().canFinish(4, new int[][]{
                {1,0}, // 修课程 1 必须修课程 0
                {2,1}, // 修课程 2 必须修课程 1
                {1,3} // 修课程 1 必须修课程 3
        }));
    }

    /**
     * [
     *  [1,0], // 想选课程1必须先选课程0, 0---->1
     *  [0,1]
     * ]
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<>();
        int[] indegree = new int[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {
            // 0--------->1, 1的入度加1
            indegree[prerequisites[i][0]]++;
        }

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                // 入度为0的全部放进队列
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;

            for (int i = 0; i < prerequisites.length; i++) {
                if (prerequisites[i][1] == course) {

                    indegree[prerequisites[i][0]]--; // 相应的课程出度--

                    if (indegree[prerequisites[i][0]] == 0) { // 始终入出度为 0 的
                        queue.offer(prerequisites[i][0]);
                    }
                }
            }

        }

        return count == numCourses;
    }

}
